package leetcode.part2;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-interview-150">...</a>
 * 三数之和
 */
public class S15 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<>();
        int k=0;
        for (;k< nums.length-2;k++){
            if (k>0&&nums[k]==nums[k-1]) continue;
            int i=k+1;
            int j=nums.length-1;
            while (i<j){
                if (nums[k]+nums[i]+nums[j]>0){
                    j--;
                } else if (nums[k]+nums[i]+nums[j]<0) {
                    i++;
                }else {
                    List<Integer> list=new ArrayList<>();
                    list.add(nums[k]);
                    list.add(nums[i]);
                    list.add(nums[j]);
                    res.add(list);
                    while (i<j&&nums[i]==nums[++i]);
                    while (i<j&&nums[j]==nums[--j]);

                }
            }
        }

        return res;
    }

    @Test
    public void test(){
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum(nums));
    }
}
